package leetcode.hot100;

import java.util.HashMap;

@SuppressWarnings("all")
public class _128_最长连续序列_深度优先 {

    // 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
    // 设计并实现时间复杂度为 O(n) 的解决方案
    // 输入：nums = [100,4,200,1,3,2]
    // 输出：4
    // 解释：最长数字连续序列是 [1, 2, 3, 4]，它的长度为 4

    HashMap<Integer, Integer> map;
    int[] nums;

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        map = new HashMap<>();
        this.nums = nums;
        // 初始化哈希表，key存放具体元素，value存放该元素出现的次数
        for (int num : nums) {
            map.put(num, 1);
        }
        // 得到每个元素的最长序列
        for (int num : nums) {
            forward(num);
        }
        // 返回哈希表中出现数字连续的最长序列
        return maxCount(map);
    }

    private int forward(int num) {
        // 递归后下一个连续的 num + 1 不存在马上就收敛返回
        if (!map.containsKey(num)) return 0;
        // 获取当前 num 出现的次数
        int i = map.get(num);
        // 说明不是第一次出现了，已经统计过了直接收敛返回，不用重复操作
        if (i > 1) return i;
        // 从num开始一直向后递归判断是否存在相邻的key，一直深度遍历到最后一个连续的key，然后每次收敛返回一层都加1个key
        // 收敛到最初的num就是该num开始的最长序列长度
        i = forward(num + 1) + 1;
        // 更新它的value为其开始的最长序列个数
        map.put(num, i);
        return i;
    }


    private int maxCount(HashMap<Integer, Integer> map) {
        int max = 0;
        // 找到当前哈希表中最长的序列长度
        for (Integer value : map.values()) {
            max = Math.max(value, max);
        }
        return max;
    }

}
